package club.xiaojiawei.queueandstack;

import java.util.*;
import java.util.stream.Stream;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/8/22 4:05 PM
 * @question 347. 前 K 个高频元素
 * @description 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 */
public class TopKFrequent347 {

    public static void main(String[] args) {
        int[] nums = {3,2,2,1,3,3};
        int[] result = topKFrequent2(nums, 2);
        System.out.println(Arrays.toString(result));
    }

    /**
     * HashMap
     * 先用HashMap统计每个数的出现次数，然后对这些进行排序
     * @param nums
     * @param k
     * @return
     */
    public static int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, int[]> map = new HashMap<>();
        for (int num : nums) {
            int[] ints = map.getOrDefault(num, new int[]{num, 0});
            ints[1]++;
            map.put(num, ints);
        }
        Collection<int[]> values = map.values();
        Stream<int[]> sorted = values.stream().sorted((i1, i2) -> i2[1] - i1[1]);
        Object[] x = sorted.toArray();
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = ((int[])x[i])[0];
        }
        return result;
    }

    /**
     * 民间-用数组代替HashMap,典型的空间换速度，且用计数排序的思想统计每个数的频率
     * @param nums
     * @param k
     * @return
     */
    public static int[] topKFrequent2(int[] nums, int k) {
        if (nums.length == 1){
            return nums;
        }
        // 考虑用数组取代哈希表统计频率，通过max和min得到数据范围得到数组大小
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] > max) max = nums[i];
            if (nums[i] < min) min = nums[i];
        }
        int maxFre = 0;
        int[] count = new int[max - min + 1];
        for (int i = 0; i < nums.length; i++){
            maxFre = Math.max(maxFre, ++count[nums[i] - min]);
        }
        maxFre++;
        // 以频率作为索引填充数组，实现排序
        // 存在频率相同的情况，所以使用list类型数组
        List<Integer>[] list = new ArrayList[maxFre];
        for (int i = 0; i < count.length; i++) {
            if (count[i] > 0) {
                if(list[count[i]] == null) list[count[i]] = new ArrayList();
                list[count[i]].add(i + min);
            }
        }

        int[] res = new int[k];
        int j = 0;
        // 获取频率前k高的元素
        for (int i = maxFre - 1; k > 0 && i >= 0; i--)  {
            if (list[i] != null){
                // 该频率可能对应多个数
                for (int l = 0; l < list[i].size(); l++){
                    res[j++] = list[i].get(l);
                    k--;
                }
            }
        }
        return res;
    }
}